Augmented reality (AR) is a live view of a physical, real-world environment whose elements are augmented by computer-generated graphics. Information about the augmented objects is overlaid onto the real world. Augmentation is conventionally in real time and in visual context with environmental elements. With the help of advanced AR technology, the information about the surrounding real world of the user becomes interactive and digitally manipulable. Because AR brings out the components of the digital world into a person's perceived real world, the user experiences and interacts with the augmented reality, depending on the level of photo-realism of the augmented objects and their integration with the real environment.
In prior art, the graphics used in AR were based on the conventional raster technology. However, raster graphics are very mediocre due to the tradeoff of quality and speed, in favor of speed. Its visual context lacks such necessary elements of photo-realism as reflections, refractions, color bleeding, color bleeding, caustics, etc. In prior art, a high quality computer-generated realism is found in the film industry, enabled through the use of ray tracing computer-generated graphics.
Ray tracing is a computer graphics technique for generating images by tracing the rays of light and simulating the effects of their encounters with virtual objects. The idea behind ray-tracing is to find mathematical solutions to compute the intersection of a ray with various types of geometry, by solving the visibility between points. This technique is capable of producing a high visual realism. In low-end ray tracing, light sources are the only illuminating objects in the scene.
More realistic imaging is delivered by a high-end ray tracing, called path tracing, which is based on global illumination. Global illumination takes into account not only the light which comes directly from a light source, but also subsequent cases in which light is returned by other surfaces in the scene, whether reflective or not.
Path tracing, referred to as Monte Carlo ray tracing, renders a 3D scene by randomly tracing samples of possible light paths. Repeated sampling for any given pixel in the image will eventually cause the average of the samples to converge to the correct solution of a rendering equation, making it one of the most physically accurate 3D graphic rendering methods in existence. Path tracing can generate images that are faithful to reality, and are indistinguishable from photographs (e.g. The Avatar movie). The visual quality is higher than that of ray tracing, but at a much greater computational cost.
The most time-consuming tasks in the ray tracing of prior art are traversals of acceleration structures, as well as intersection tests between rays and polygons. Every single ray is traversed across an accelerating structure (e.g. K-trees or BVH trees), seeking polygons that are candidates for intersection. These traversals become a major time-consuming action—they typically take 60%-70% of the image generation time. Then, all candidate polygons associated with the search must undergo a line-triangle intersection test, to determine the earliest hit along the ray's path.
The layout of the prior art ray tracing method is depicted in FIG. 1. First, an acceleration structure must be constructed 10. The construction is done as a preprocessing step, and takes much more time than generating a single image. Generally, the construction time depends on the scene size. The bigger the scene, the longer the construction time. Every major modification in the scene necessitates a reconstruction of the acceleration structure. The memory size is typically doubled by the acceleration structure. Tracing of rays 12 is based on massive traversals of the acceleration structure 11, when each ray is traversed across the structure in search of intersections between the ray and various scene objects. The resulting intersection points are lighted, textured, shaded 13, and aggregated into image pixels.
There are two major drawbacks associated with the use of acceleration structures in ray tracing of prior art; (i) they must be repeatedly reconstructed for scene changes, and (ii) traversals of these structures are time-consuming. Both disadvantages contradict with the real-time requirements of AR.
Therefore, the primary object of the present invention is to accelerate the performance of global illumination ray tracing up to real time, making it suitable for AR.
Another object of the present invention is to reduce the computational complexity of ray tracing.
Another object of the present invention is to reduce the power consumption of ray tracing.
Another object of the present invention is to enable global illumination ray tracing by the processing level of consumer computing devices.